%
%% Deterministic Part
%%
%% A Review of the Seventh International Planning Competition
%% AI Magazine
%%
%% ----------------------------------------------------------------


\section{Deterministic Track}
\label{sec:deterministic}

The deterministic part of the competition is the longest-running track.  Its focus is on the ability of planners to solve problems across a wide range of unseen domains: a challenging test of the ability of planners to succeed as domain-independent systems.  Several sub-tracks of the competition have developed over the years, with all tracks at the centre of Figure~\ref{fig:competitionhistory} being considered sub-tracks of the deterministic competition.  The 2011 competition saw the introduction of a new track for multi-core planners.  Furthermore, another key contribution was to release all the software used to run the competition\footnote{available at {\scriptsize \url{http://www.plg.inf.uc3m.es/ipc2011-deterministic/FrontPage/Software}}}, thus reducing workload for future potential organisers.

The 2011 competition followed the successful 2008 competition, and was run
in a very similar way.  For 2011 we decided to keep the language the
same, without introducing extensions, as planners still need to `catch
up' with the currently available features. We also made use of the
plan validator VAL~\cite{howey.r.long.d.ea:val}. We maintained the
evaluation metrics introduced in IPC-2008, favouring quality and coverage
over problem-solving speed. Briefly, each planner is allowed 30 minutes on each
planning task, and receives a score between 0 and 1. The score is the ratio
between the quality of the solution found,
if any (if not, it is given zero), and the quality of the best
solution found by any entrant. The score is summed across all problems
for a given planner: the winner and runner up for each track being
those with the highest scores. Scores are not aggregated amongst tracks.
We included in the results a comparison to the winner of the last
competition to ensure progress is being made.

The 2011 competition was extremely popular: a record number of 55 entrants took part in the deterministic track alone, almost eight and three times more than the first and sixth competitions respectively, showing significant growth in community involvement.  A summary of each of the sub-tracks follows.


\begin{figure}
 \includegraphics[width=\columnwidth]{competitionhistory}
 \caption{The History of the International Planning Competition}
 \label{fig:competitionhistory}
\end{figure}

\subsection{Satisficing Track} 

{\sc Lama} won the satisficing track for the second year running, in its new incarnation {\sc Lama-2011} (Richter, Westphal, Helmert \& R\"oger).  {\sc Lama} follows in a long history of successful planners using forward-chaining search --- including previous winners {\sc Hsp} (Bonet \& Geffner) in 1998, {\sc FF} (Hoffmann) in 2000 and {\sc Fast Downward} (Helmert \& Richter) in 2004 --- with further guidance obtained from landmarks (facts that must be true in any solution plan).  Interestingly the only non-forward-search planner to win this track was {\sc Lpg} (Gerevini \& Serina) in 2002, using stochastic local search.  A number of other interesting techniques have been seen throughout the years, including the use of pattern databases, and planning as satisfiability.  9 out of 27 of the planners in 2011 outperformed the 2008 winner {\sc Lama-2008} (Richter \& Westphal), showing good progress in the state-of-the-art.

\subsection{Multi-Core Track} 

With the advent of parallel computers at affordable prices we wanted to ask the question: can planners using multiple cores at the same time perform better than using the single core allowed in the classical track?  The winner of the multi-core track was {\sc ArvandHerd} (Nakhost, Mueller, Schaeffer, Sturtevant \& Valenzano); but it did not outperform the classical-track winner, {\sc Lama-2011}.  This is not so concerning, however --- the history of the IPC shows that classical planners are highly engineered in terms of data structures, and are difficult to beat in the first editions of new tracks.

\subsection{Temporal Track} 

Since the introduction of PDDL 2.1 in 2003, only a subset of the temporal planners available have been able to reason with the full temporal semantics of the language.  As such, for the 2011 temporal track, we included a special class of temporal problems that include required concurrency~\cite{mausamTime}.  That is, no solution to the problem exists if the planner is not able to run two actions in parallel at the same time.  The most successful planners in this track were the winner {\sc Daeyahsp} (Dr\'eo, Schoenauer, Sav\'eant \& Vidal) and runner up ex-aequo {\sc Yahsp2-mt} (Vidal) which performed best on the standard temporal problems, and runner up ex-aequo {\sc Popf2} (Coles, Coles, Fox \& Long), which was the only planner to solve problems in all domains with required concurrency.

\subsection{Optimal Track} 

As planning technology develops, writing planners that find optimal, as opposed to simply satisfying, solutions to problems becomes more feasible.  {\sc Fast Downward Stone Soup 1} (Helmert, Hoffmann, Karpas, Keyder, Nissim, Richter, R\"oger, Seipp \& Westphal) won this year's competition outperforming the new version of the 2008 winner, {\sc Gamer} (Edelkamp \& Kissmann). {\sc Fast Downward Stone Soup} is portfolio based, in contrast to the symbolic search using BDDs of {\sc Gamer}. The major shift towards forward search and away from planning as satisfiability in the two most recent competitions can be attributed to a change in the definition of optimality: the last two competitions have required a lowest-cost plan; whereas previous editions required a solution with the minimum number of actions. The former is much less amenable to a planning as satisfiability approach.


~\nocite{long.d.fox.m:3rd} %Third IPC
~\nocite{fox.m.long.d:pddl2}%PDDL2.1
~\nocite{hoffmann.j.edelkamp.s:deterministic}% IPC4
~\nocite{gerevini.ae.haslum.p.ea:deterministic} %IPC5
~\nocite{gerevini.a.long.d:plan} %pddl3

